package com.work.daily;

import java.util.*;

/**
 * title : 前 K 个高频元素
 * content : 输入: nums = [1,1,1,2,2,3], k = 2 ;输出: [1,2]
 * solution : 利用堆.PriorityQueue构建方式不同
 * link :
 * Created by suk on 2020/9/7.
 */
public class D10_TopKFrequent_347_03_Heap {

    public static void main(String[] args) {
        int[] nums = {1, 2, 1, 3, 2, 2, 3, 3, 3};
        int k = 2;
        D10_TopKFrequent_347_03_Heap d10 = new D10_TopKFrequent_347_03_Heap();
        System.out.println(Arrays.toString(d10.topKFrequent(nums, k)));
    }
    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<>();
        // 注意getOrDefault的用法
        for (int num : nums) {
            int i = map.getOrDefault(num, 0);
            map.put(num, i + 1);
        }

        // 对value进行排序
        // int[] 0存key, 1存value . 思路学习下
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {

                return o1[1] - o2[1];
            }
        });

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (queue.size() < k)
                queue.offer(new int[]{entry.getKey(), entry.getValue()});
            else {
                // 注意peek和element的区别.
                // 注意poll和remove的区别.
                if (entry.getValue() > queue.peek()[1]) {
                    queue.poll();
                    queue.offer(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }

        int[] result = new int[k];
        int i = 0;
        while (!queue.isEmpty()) {
            result[i++] = queue.poll()[0];
        }

        return result;
    }
}
